package offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Offer38 {

    List<Character> path1= new ArrayList<>();;
    List<String > result1=new ArrayList<>();
    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        char[] sort = sort(chars);
        boolean[]  record=new boolean[sort.length];
        Arrays.fill(record,false);
        backtracking(chars,record);
        String[] array = result1.stream().toArray(String[]::new);
        return array;
    }


    public   char[]  sort(char[]  c){
        for (int i = 0; i < c.length - 1; i++) {      //长度-1,目的就是为了不会出现数组索引超出的异常
            for (int j = 0; j < c.length - 1; j++) {//
                if ((int) c[j] > (int) c[j + 1]) {//如果相邻的两条数据，前面的比后面的大，就交换顺序。
                    char temp = c[j];
                    c[j] = c[j + 1];
                    c[j + 1] = temp;
                }
            }
        }
        return  c;
    }


//    String str = "abc";
//    char[] chars = str.toCharArray();
//Arrays.sort(chars);
//
//    String sortedStr = new String(chars);
//System.out.println(sortedStr);


    public void backtracking(char[] chars, boolean[]  record) {
        if (path1.size()== chars.length){
            StringBuilder stringBuilder = new StringBuilder();
            for (Character character : path1) {
                stringBuilder.append(character);
            }
            String result = stringBuilder.toString();
            System.out.println(result);
            result1.add(result);
            return;
        }

        for (int i = 0; i < chars.length; i++) {
            if (i>0&&chars[i]==chars[i-1]&&record[i-1]==false){
                continue;
            }
           if (record[i]==false){
               record[i]=true;
               path1.add(chars[i]);
               backtracking(chars,record);
               record[i]=false;
               path1.remove(path1.size()-1);
           }
        }
    }



    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backTrack(nums, used);
        return result;
    }

    private void backTrack(int[] nums, boolean[] used) {

        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
//     used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
//     used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
//     如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
//     如果同⼀树⽀nums[i]没使⽤过开始处理
            if (used[i] == false) {
                used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
                path.add(nums[i]);
                backTrack(nums, used);
                path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
                used[i] = false;//回溯
            }
        }
    }

    public static void main(String[] args) {
        Offer38 offer38 = new Offer38();
//        int[]  nums={1,2,3};
//        List<List<Integer>> list = offer38.permuteUnique(nums);
//        for (List a:
//             list) {
//            for (int i = 0; i < a.size(); i++) {
//                System.out.print(a.get(i));
//            }
//            System.out.println("=");
//
//        }

        String[] abcs = offer38.permutation("abc");
        System.out.println(Arrays.toString(abcs));
    }

}